นิยามแบบเป็นทางการของเอ็นพีมีสองแบบ

นิยามแบบแรก -- เครื่องจักรทัวริงเชิงไม่กำหนด

เราจะกล่าวว่าปัญหาการตัดสินใจ π {\displaystyle \pi } อยู่ภายในเอ็นพี เมื่อ เราสามารถหาเครื่องจักรทัวริงเชิงไม่กำหนด M ที่มีคุณสมบัติดังต่อไปนี้

• M ทำงานจบภายในจำนวนเสตปที่เป็นฟังก์ชันพหุนามกับขนาดของอินพุต
• ถ้า x เป็นตัวอย่างของปัญหาที่ตอบว่า "ใช่" จะมีอย่างน้อย 1 เส้นทางการคำนวณ (computation path) ของ M(x) ที่ให้คำตอบว่า "ใช่"
• ถ้า x เป็นตัวอย่างของปัญหาที่ตอบว่า "ไม่ใช่" ทุกเส้นทางการคำนวณของ M(x) จะให้คำตอบว่าไม่ใช่

ลองมาดูตัวอย่างกันสักสองสามตัวอย่าง

เริ่มจากปัญหาที่เข้าใจได้ง่าย พิจารณาปัญหา "จำนวน x เป็นจำนวนประกอบหรือไม่?" ปัญหานี้จะตอบว่า "ใช่" ถ้าจำนวนที่กำหนดให้เป็นจำนวนประกอบ สำหรับปัญหานี้เราสามารถออกแบบเครื่องจักรทัวริงเชิงไม่กำหนดให้ทำงานดังต่อไปนี้

    M(x)      เลือกจำนวน y ที่มีค่ามากกว่า 2 แต่น้อยกว่า x มา 1 จำนวน          ถ้า y หาร x ลงตัว ตอบว่า "ใช่"     ตอบว่า "ไม่ใช่"

พิจารณาการทำงานของเครื่องจักรทัวริงในสองกรณี กรณีแรก ถ้า x เป็นจำนวนประกอบ จะมีทางเป็นไปได้ว่าจำนวน y ที่ M เลือกจะหาร x ลงตัว กรณีที่สอง ถ้า x ไม่ใช่จำนวนประกอบ ไม่ว่า M จะเลือกจำนวนใดมาก็ตาม คำตอบที่ได้จะเป็น "ไม่ใช่" เสมอ จากการมีอยู่ของ M ดังกล่าว เราสามารถสรุปได้ว่าปัญหานี้อยู่ในเอ็นพี

ถัดมา พิจารณา ปัญหาความสอดคล้องแบบบูล เราสามารถออกแบบเครื่องจักรทัวริงเชิงไม่กำหนดดังต่อไปนี้ โดยเครื่องจักร M จะรับนิพจน์ ϕ ( x 1 , x 2 , … , x n ) {\displaystyle \phi (x_{1},x_{2},\ldots ,x_{n})} มา แล้วตัดสินว่านิพจน์นี้สามารถแทนค่า x 1 , x 2 , … , x n {\displaystyle x_{1},x_{2},\ldots ,x_{n}} เพื่อทำให้นิพจน์เป็นจริงได้หรือไม่

                      M        (        ϕ        )              {\displaystyle M(\phi )}      for i :=1 to n        เลือกค่า                               x                      i                                {\displaystyle x_{i}}   จาก (true, false)     แทนค่าที่เลือกทั้งหมดลงใน                     ϕ              {\displaystyle \phi }   แล้วตอบว่า "ใช่" ถ้า                     ϕ              {\displaystyle \phi }   เป็นจริง ถ้าไม่งั้นแล้วให้ตอบ "ไม่ใช่"

นิยามแบบที่สอง -- การตรวจคำตอบ

เราจะกล่าวว่าปัญหาการตัดสินใจ π {\displaystyle \pi } อยู่ภายในเอ็นพี เมื่อ เราสามารถหาเครื่องจักรทัวริงเชิงกำหนด V ที่มีคุณสมบัติดังต่อไปนี้ (V เป็นตัวแทนของ verifier)

• V ทำงานจบภายในเวลาที่เป็นฟังก์ชันพหุนามกับขนาดของอินพุต
• ถ้า x เป็นตัวอย่างของปัญหาที่ตอบว่า "ใช่" จะมีบทพิสูจน์ w ที่ทำให้ V(x,w) ตอบว่า "ใช่"
• ถ้า x เป็นตัวอย่างของปัญหาที่ตอบว่า "ไม่ใช่" ไม่ว่าบทพิสูจน์ w จะเป็นอะไรก็ตาม V(x,w) จะตอบว่า "ไม่ใช่"
• บทพิสูจน์ w มีขนาดเป็นฟังก์ชันพหุนามกับขนาดของอินพุต

หมายเหตุ: w มีชื่อเรียกหลายแบบ ที่นิยมเรียกกันก็คือ พยาน (witness) , บทพิสูจน์ (proof) , และ certificate

ลองมาดูตัวอย่างเดียวกันแต่ใช้นิยามของเอ็นพีแบบที่สองในการพิสูจน์ดูบ้าง เริ่มจากปัญหาจำนวนประกอบก่อน เราสามารถออกแบบ V ได้ดังนี้

    V(x,w)      ถ้า w หาร x ลงตัว ตอบว่า "ใช่"     ตอบว่า "ไม่ใช่"

สังเกตว่าถ้า x เป็นจำนวนประกอบ จะมีบทพิสูจน์ w (ซึ่งในที่นี้ บทพิสูจน์ก็คือจำนวนที่หารจำนวนประกอบ x ลงตัว) ที่ทำให้ V ตอบว่า "ใช่" แต่ในทางกลับกันหาก x เป็นจำนวนเฉพาะ จะไม่มีบทพิสูจน์ใดที่ทำให้ V ตอบว่า "ใช่"

ลองมาดูตัวอย่างของ ปัญหาความสอดคล้องแบบบูล อีกครั้ง เราสามารถออกแบบ V ได้โดย

                      V        (        ϕ        ,        w        )              {\displaystyle V(\phi ,w)}      ถ้า w ไม่อยู่ในรูปแบบของ                     w        =                  w                      1                                    w                      2                          …                  w                      n                                {\displaystyle w=w_{1}w_{2}\ldots w_{n}}   ตอบว่า "ไม่ใช่"     แทนค่า                     ϕ        (                  w                      1                          ,                  w                      2                          ,        …        ,                  w                      n                          )              {\displaystyle \phi (w_{1},w_{2},\ldots ,w_{n})}   แล้วตอบว่า "ใช่" ถ้า                     ϕ              {\displaystyle \phi }   เป็นจริง ถ้าไม่งั้นแล้วให้ตอบ "ไม่ใช่"

จะเห็นว่าในปัญหานี้บทพิสูจน์ของเราก็คือค่าของตัวแปรที่ทำให้นิพจน์เป็นจริงนั่นเอง

การสมมูลกันของนิยาม

เนื้อหาในส่วนนี้จะกล่าวถึงแนวคิดของบทพิสูจน์ว่าทำไมนิยามทั้งสองแบบนี้จึงสมมูลกันได้ การพิสูจน์แยกออกเป็นสองส่วนในส่วนแรกต้องพิสูจน์ว่าหากเซ็ต A ถูกจัดว่าเป็นเอ็นพีตามนิยามแบบแรกแล้ว A จะต้องเป็นเอ็นพีตามนิยามแบบที่สองด้วย และในส่วนที่สองเราต้องพิสูจน์ในกรณีกลับกัน

นิยามแบบแรก → {\displaystyle \rightarrow } นิยามแบบที่สอง

สมมติว่าปัญหา A มีเครื่องจักรทัวริงเชิงไม่กำหนด M ที่ใช้เวลาการคำนวณเป็นฟังก์ชันพหุนามกับขนาดของอินพุต เราสามารถสร้างเครื่องจักรทัวริงเชิงกำหนด V ที่ simulate M โดยพิจารณาบทพิสูจน์ที่จะตรวจสอบคือบิตสตริงที่บ่งบอกถึงทางเลือกของ M และ V จะตอบ "ใช่" หากท้ายสุดแล้วสตริงที่บ่งบอกทางเลือกทำให้ M ทำงานจบในสถานะที่ตอบ "ใช่" เราลองมาวิเคราะห์การทำงานของ V กันดู

• หาก x เป็นตัวอย่างของปัญหาที่ตอบ "ใช่" บทพิสูจน์ที่เป็นทางเลือกที่ทำให้ A ตอบรับจะผ่านการตรวจสอบของ V
• หาก x เป็นตัวอย่างของปัญหาที่ตอบ "ไม่ใช่" จะไม่มีบทพิสูจน์ใดที่ผ่านการตรวจสอบของ V ได้

มีรายละเอียดปลีกย่อยที่ต้องจัดการอีกหน่อยคือ M อาจจะมีจำนวนทางเลือกมากกว่าสองในการเลือกแต่ละครั้ง ทำให้ไม่สามารถใช้บิตสตริงในการกำหนดทางเลือกได้ กรณีนี้สามารถแก้ได้ง่ายโดยการแปลง M ไปเป็น M ′ {\displaystyle M'} โดยที่ทุกครั้งที่ M ′ {\displaystyle M'} ใช้สมบัติการเลือกของเครื่องจักรทัวริงเชิงไม่กำหนด ทางเลือกของ A ′ {\displaystyle A'} จะมีเพียงสองเท่านั้น

นิยามแบบที่สอง → {\displaystyle \rightarrow } นิยามแบบแรก

สมมติว่าปัญหา A เป็นเอ็นพีตามนิยามแบบที่สอง นั่นก็คือมีเครื่องจักรทัวริงเชิงกำหนด V ที่ทำหน้าที่ในการตรวจสอบตามนิยาม เราสามารถสร้างเครื่องจักรทัวริงเชิงไม่กำหนด M ที่รับอินพุต x ที่สอดคล้องกับนิยามแบบแรกโดยการให้ M ใช้ความสามารถของเครื่องจักรทัวริงเชิงไม่กำหนดในการเลือกบทพิสูจน์ w สำหรับ V หลังจากนั้น M simulate การทำงานของ V(x,w) และ M ตอบรับเมื่อ V(x,w) ให้คำตอบว่า "ใช่" เราสามารถวิเคราะห์เป็นสองกรณีได้ในวิธีเดียวกันกับบทพิสูจน์ในส่วนแรก